package com.example.algorithm.dynamicprogramming;

/**
 * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * 示例 1：
 * 输入：k = 2, prices = [2,4,1]
 * 输出：2
 * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
 * <p>
 * 示例 2：
 * 输入：k = 2, prices = [3,2,6,5,0,3]
 * 输出：7
 * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 * 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3。
 */
public class Leetcode188_MaxProfitIV {
    static class Solution {
        /**
         * 动态规划：根据LeetCode123 可以得出
         * 每一天结束之后，有可能处于以下 (2k + 1) 种状态之一：
         * 1:没有买股也没有卖股。
         * 2:买了第一支股，但是还没有卖出第一支股。
         * 3:买了第一支股，并且卖出第一支股。
         * 4:买了第一支股，并且卖出第一支股，买了第二支股，但是还没有卖出第二支股。
         * 5:买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股。
         * ...
         * 2k:买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股... 买了第 k 支股，但是还没有卖出
         * 2k + 1:买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股... 买了第 k 支股，并且卖出第 k 支股
         *
         * @param k
         * @param prices
         * @return
         */
        public int maxProfit(int k, int[] prices) {
            if (prices == null || prices.length * k == 0) return 0;
            int size = prices.length, maxTradeCounts = Math.min(k, size / 2);  // n 天最多只能进行 n / 2 笔交易
            // dpBuys[i][j] 表示在第 i 天(prices[0..i]) 进行恰好 j 笔交易，并且当前手上持有一支股票(已经完成了 j - 1 支股的交易，且买了第 j 支股，但还没卖出)能获得的最大利润
            // dpSells[i][j] 表示在第 i 天(prices[0..i])恰好进行 j 笔交易，并且当前手上不持有股票(已经完成了 j - 1 支股的交易，且买了第 j 支股，并且卖出第 j 支股)能获得的最大利润
            int[][] dpBuys = new int[size][maxTradeCounts + 1];
            int[][] dpSells = new int[size][maxTradeCounts + 1];
            for (int j = 0; j <= maxTradeCounts; j++) dpBuys[0][j] = -prices[0];
            for (int i = 1; i < size; i++) {
                dpBuys[i][0] = Math.max(dpBuys[i - 1][0], dpSells[i - 1][0] - prices[i]);
                for (int j = 1; j <= maxTradeCounts; j++) {
                    dpBuys[i][j] = Math.max(dpBuys[i - 1][j], dpSells[i - 1][j] - prices[i]);
                    dpSells[i][j] = Math.max(dpSells[i - 1][j], dpBuys[i - 1][j - 1] + prices[i]);
                }
            }
            return dpSells[size - 1][maxTradeCounts];

            //// 空间优化写法
            //// 因为prices[0..i] 的交易只和prices[0..i-1]有关(可以将前面的结果进行覆盖)，
            //// 所以可以使用一维数组就可以表示出第 i 天(prices[0..i]) 进行恰好 j 笔交易的状态
            //// buys[i] 表示进行恰好 i 笔交易，并且当前手上持有一支股票(已经完成了 i - 1 支股的交易，且买了第 i 支股，但还没卖出)能获得的最大利润
            //// sells[i] 表示进行恰好 i 笔交易，并且当前手上不持有股票(已经完成了 i - 1 支股的交易，且买了第 i 支股，且卖出)能获得的最大利润
            //int[] buys = new int[maxTradeCounts + 1], sells = new int[maxTradeCounts + 1];
            //for (int i = 0; i < maxTradeCounts; i++) buys[i] = -prices[0];
            //for (int i = 1; i < size; i++) {
            //    buys[0] = Math.max(buys[0], sells[0] - prices[i]);
            //    for (int j = 1; j <= maxTradeCounts; j++) {
            //        buys[j] = Math.max(buys[j], sells[j] - prices[i]);
            //        sells[j] = Math.max(sells[j], buys[j - 1] + prices[i]);
            //    }
            //}
            //return sells[maxTradeCounts];
        }
    }

    public static void main(String[] args) {
        int k = 2;
        int[] prices = {3, 2, 6, 5, 0, 3};
        System.out.println(new Solution().maxProfit(k, prices));
    }
}
